package algebra.visitors;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

import option.KBVocabulary;

import algebra.op.ProjectionOP;
import algebra.query.pd.*;

import kb.DescriptionLogicsKB;
import tableaux.Completion;
import utils.Util;
import utils.exception.CoreReasoningException;
import utils.exception.ProjectionException;
import utils.opt.CacheTree;
import entities.Individual;
import entities.assertion.ConceptAssertion;
import entities.assertion.StarConceptAssertion;
import entities.concept.AndConcept;
import entities.concept.Concept;
import entities.concept.DomainConceptEQ;
import entities.concept.DomainConceptLT;
import entities.concept.DomainConceptLTEQ;
import entities.concept.ExistsConcept;
import entities.concept.NotConcept;
//import entities.concept.NotConcept;
import entities.concept.OrConcept;
import entities.role.GeneralRolePath;
import entities.role.Role;

public class ProjectionOPEvaluator {
	// public static final boolean allowMissingFeaturePatching = false;
	private static boolean ENABLE_OPTIMIZATIONS = true;
	private static boolean ENABLE_CACHETREE = false;
	private static int structuralSubsumptions = 0;
	private static final boolean ChooseLongestEqConcept = true;
	private DescriptionLogicsKB kb;

	public ProjectionOPEvaluator(DescriptionLogicsKB kb) {
		super();
		this.kb = kb;
	}

	public DescriptionLogicsKB getKB() {
		return this.kb;
	}

	public static int getStructuralSubsumptions() {
		return structuralSubsumptions;
	}

	public ConceptAssertion visitPipelined(ProjectionOP pq,
			ConceptAssertion subres) {
		ConceptAssertion ret = null;
		ProjDesc pd = pq.getPrjDesc();
		if (AlgebraicOPEvaluator.isSpecialAssertion(subres)) {
			StarConceptAssertion sca = (StarConceptAssertion) subres;
			try {
				ret = (projectFinal(sca, pd, null, true));
			} catch (ProjectionException e) {
				e.printStackTrace();
			}
		} else {
			try {
				ret = (projectFinal(subres, pd, null, false));
			} catch (ProjectionException e) {
				e.printStackTrace();
			}
		}
		return ret;
	}

	/*
	 * Given (a:C, pd), compute a:LCS.
	 */
	public List<ConceptAssertion> visit(ProjectionOP pq) {
		List<ConceptAssertion> res = new LinkedList<ConceptAssertion>();
		ProjDesc pd = pq.getPrjDesc();
		AlgebraicOPEvaluator eval = new AlgebraicOPEvaluator();
		List<ConceptAssertion> subres = null;
		try {
			subres = pq.getSubquery().acceptVisitor(eval);
		} catch (CoreReasoningException e1) {
			e1.printStackTrace();
		}
		if (AlgebraicOPEvaluator.isSpecialAssertion(subres)) {
			// star semantics, use a representative assertion for testing
			StarConceptAssertion sca = (StarConceptAssertion) subres.get(0);
			try {
				res.add(projectFinal(sca, pd, null, true));
			} catch (ProjectionException e) {
				e.printStackTrace();
			}
		} else {
			for (ConceptAssertion ca : subres) {
				try {
					res.add(projectFinal(ca, pd, null, false));
				} catch (ProjectionException e) {
					e.printStackTrace();
				}
			}
		}
		return res;
	}

	public ConceptAssertion projectFinal(ConceptAssertion ca,
			ProjDesc pd, GeneralRolePath grp, boolean star)
			throws ProjectionException {
		// star or standard semantics
		List<Concept> res = project(ca, pd, grp);
		Concept desc = null;
		if (res.size() > 1) {
			desc = new AndConcept(res);
		} else if (res.size() == 1) {
			desc = res.get(0);
		} else {
			desc = KBVocabulary.CONCEPT_TOP;
		}
		Individual ind = null;
		if (star) {
			ind = KBVocabulary.SPECIAL_IND;
		} else {
			ind = ca.getIndividual();
		}
		return new ConceptAssertion(ind, desc);
	}

	private List<Concept> project(ConceptAssertion ca,
			ProjDesc pd, GeneralRolePath grp)
			throws ProjectionException {
		if (grp == null) {
			grp = new GeneralRolePath();
		}
		if(pd instanceof PdConcept){
				return projectConcept(ca, ((PdConcept) pd).getConcept(), grp);
			}else if(pd instanceof PdFeature){
				return reduce(projectFeature(ca, ((PdFeature) pd).getFeature(), grp), grp, this.kb);
			}else if(pd instanceof PdConjunction){
				return projectJoin(ca, ((PdConjunction) pd).getSubPd1(), 
						((PdConjunction) pd).getSubPd2(), grp);
			}else if(pd instanceof PdRole){
				return reduce(projectRole(ca, ((PdRole) pd).getRole(), 
						((PdRole) pd).getSubPd(), grp), grp,
						this.kb);
			}else{
				throw new ProjectionException("Unrecognized Projection Type: "
						+ pd + "\n" + pd.toString());
			}

	}

	/**
	 * 
	 * @param ca
	 *            : the condition
	 * @param c1
	 *            : the projection description concept?
	 * @param rp
	 *            : role path
	 * @param tb
	 *            ,ab: the knowledge base
	 * @return
	 */
	private List<Concept> projectConcept(ConceptAssertion ca, Concept c1,
			GeneralRolePath grp) {
		// Case 1. C under exists R. (C1), return {C1}
		List<Concept> result = new LinkedList<Concept>();
		if (Completion.partiallyGuardedReasoning && grp == null && c1.isTop()) {
			result.add(KBVocabulary.CONCEPT_TOP);
			return result;
		}
		Concept rhs = Util.parseConceptFromGeneralRolePath(grp, c1);
		ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(), rhs);
		if (Util.assertionCheck(ca, ast, kb)) {
			result.add(c1);
			return result;
		}

		// Case 2. C under exists R. (T), return {T}
		if (grp.length() > 0) {
			rhs = Util.parseConceptFromGeneralRolePath(grp,
					KBVocabulary.CONCEPT_TOP);
			ast = new ConceptAssertion(ca.getIndividual(), rhs);
			if (Util.assertionCheck(ca, ast, kb)) {
				result.add(KBVocabulary.CONCEPT_TOP);
				return result;
			}
		}
		// Otherwise, return {}
		result.add(KBVocabulary.CONCEPT_TOP);
		return result;
	}

	private List<Concept> projectFeature(ConceptAssertion ca, Role f,
			GeneralRolePath grp) throws ProjectionException {
		List<Concept> result = new LinkedList<Concept>();
		if (ENABLE_CACHETREE) {
			// retrieve the cache for possible matches
			HashSet<String> potres = CacheTree.findCacheForFeature(
					ca.getIndividual(), grp, f);
			if (potres.size() > 0) {
				// System.out.println("Role path:"+grp+"; cache for "+f+": "+potres);
				List<String> listOfConstants = new ArrayList<String>();
				listOfConstants.addAll(potres);
				Collections.sort(listOfConstants, new Comparator<String>() {
					public int compare(String o1, String o2) {
						return o1.compareTo(o2);
					}
				});
				result.addAll(iterativeSearchK(ca, f, grp,
						listOfConstants, 0, listOfConstants.size() - 1));
				// System.out.println(++CACHE_HIT);
				if (result.size() > 0) {
					// if no result found, resort to general reasoning
					// System.err.println("Error may be for :"+ca.getIndividual());
					return result;
				}
			}
		}

		// First try structural subsumption test
		// (ie., look for feature 'f' explicitly appearing in 'C').
		if (ENABLE_OPTIMIZATIONS) {
			if (grp == null || grp.getOffset() == 0) {
				LinkedList<GeneralRolePath> q = new LinkedList<GeneralRolePath>();
				GeneralRolePath p = new GeneralRolePath();
				p.addContent(ca.getConcept());
				q.add(p);
				while (!q.isEmpty()) {
					p = q.remove();
					Concept con = (Concept) p.getLastItem();
					if (con instanceof AndConcept) {
						for (Concept and : ((AndConcept) con).getConceptSet()) {
							GeneralRolePath testrp = new GeneralRolePath();
							testrp.addContent(and);
							q.add(testrp);
						}
					} else if (con instanceof OrConcept) {
						for (Concept or : ((OrConcept) con).getConceptSet()) {
							GeneralRolePath testrp = new GeneralRolePath();
							testrp.addContent(or);
							q.add(testrp);
						}
					} else if (p.getOffset() == 0
							&& con instanceof DomainConceptEQ) {

						if (((DomainConceptEQ<?, ?>) con).getRealFeature()
								.equals(f)) {
							structuralSubsumptions += 1;
							result.add(con);
						}
					}
				}
				// possibly more feature values are available in KB
				if (result.size() > 0) {
					return result;
				}

			}
		}
		// binary search for all
		List<String> listOfConstants = Arrays.asList(Util.getConstants());
		Collections.sort(listOfConstants, new Comparator<String>() {
			public int compare(String o1, String o2) {
				return o1.compareTo(o2);
			}
		});

		result.addAll(iterativeSearchK(ca, f, grp,
				listOfConstants, 0, listOfConstants.size() - 1));

		if (result.size() == 0) {
			result.add(KBVocabulary.CONCEPT_TOP);
		}
		// if(allowMissingFeaturePatching){
		// Concept missingFV = new DomainConceptEQ<Role, String>(new Role(f),
		// KBVocabulary.FeatureValueMissingPatch);
		// Concept toparse = Util.parseConceptFromGeneralRolePath(grp,
		// KBVocabulary.CONCEPT_TOP);
		// ConceptAssertion rhs = new ConceptAssertion(ca.getIndividual(),
		// toparse);
		// boolean addAnythingToCache = false;
		// if(result.size()>0){
		// //already obtained some f=v1 etc., so f=anything can be added without
		// question
		// addAnythingToCache = true;
		// }else
		// if(Util.assertionCheck(ca, rhs, kb)){
		// //if no f is present in the assertion,check if f=MissingValuePatch,
		// i.e., top is entailed
		// addAnythingToCache = true;
		// }
		// if(addAnythingToCache){
		// //add to cache
		// if(ENABLE_CACHETREE){
		// CacheTree.addCache(ca.getIndividual(), grp, missingFV);
		// }
		// //add to result
		// result.add(missingFV);
		// // result.add(KBVocabulary.CONCEPT_TOP);
		// }
		//
		// }
		return result;
	}

	private enum Ops {
		LT, EQ, LTEQ
	}

	private Concept formDomainConcept(Role f, String s, Ops op) {
		// if(s.equals(KBVocabulary.FeatureValueMissingPatch)){
		// if(allowMissingFeaturePatching){
		// return KBVocabulary.CONCEPT_TOP;
		// }
		// }
		switch (op) {
		case EQ:
			return new DomainConceptEQ<Role, String>(f, s);
		case LT:
			return new DomainConceptLT<Role, String>(f, s);
		case LTEQ:
			return new DomainConceptLTEQ<Role, String>(f, s);
		}
		return null;
	}

	// constants must be sorted lexicographically.
	private List<Concept> iterativeSearchK(ConceptAssertion ca, Role f,
			GeneralRolePath grp, List<String> constants, int low, int high) {
		List<Concept> result = new LinkedList<Concept>();
		if (low > high) {
			return result;
		}
		// i.e. floor value
		int mid = (low + high) >>> 1;
		Concept con;
		boolean end = low == high ? true : false;
		if (end) {
			// con = new DomainConceptEQ<Role, String>(f, constants.get(low));
			con = this.formDomainConcept(f, constants.get(low), Ops.EQ);
		}
		else {
			// low<= f <= high
			con = new AndConcept(this.formDomainConcept(f, constants.get(high),
					Ops.LTEQ), new NotConcept(this.formDomainConcept(f,
					constants.get(low), Ops.LT)));
		}
		Concept test = Util.parseConceptFromGeneralRolePath(grp, con);
		boolean specialSemantics = false;
		if (ca instanceof StarConceptAssertion  ||
				ca.getIndividual().equals(Individual.getStarIndividual())) {
			specialSemantics = true;
		}
		boolean pass = false;
		if (specialSemantics) {
			pass = Util.subsumes(ca.getConcept(), test, kb);
		} else {
			ConceptAssertion rhs = new ConceptAssertion(ca.getIndividual(),
					test);
			pass = Util.assertionCheck(ca, rhs, kb);
		}
		if (pass) {
			if (end) {
				if (ENABLE_CACHETREE) {
					CacheTree.addCache(ca.getIndividual(), grp, con);
				}
				result.add(con);
//				return result;
			} else {
				result.addAll(iterativeSearchK(ca, f, grp, constants, low, mid));
				result.addAll(iterativeSearchK(ca, f, grp, constants, mid + 1,
						high));
			}
		}
		return result;
	}

	//
	private List<Concept> projectJoin(ConceptAssertion ca,
			ProjDesc pd1, ProjDesc pd2,
			GeneralRolePath grp) throws ProjectionException {
		List<Concept> result = new LinkedList<Concept>();
		List<List<Concept>> loop = new LinkedList<List<Concept>>();
		List<Concept> subres2 = project(ca, pd2, grp);
		List<Concept> subres1 = project(ca, pd1, grp);
		loop.add(subres2);
		loop.add(subres1);
		boolean toplevel = false;
		// top level join? only need to add most specific concepts
		if (grp.getOffset() == 0) {
			toplevel = true;
		}
		int i = 0;
		while (i < loop.size()) {
			LinkedList<HashSet<Concept>> q = new LinkedList<HashSet<Concept>>();
			// initialize q
			for (Concept con : loop.get(i)) {
				HashSet<Concept> hs = new HashSet<Concept>();
				hs.add(con);
				q.add(hs);
				if (!toplevel) {
					result.add(con);
				}
			}
			for (HashSet<Concept> s2 : q) {
				int j = i + 1;
				while (j < loop.size()) {
					for (Concept d : loop.get(j)) {
						HashSet<Concept> newcd = new HashSet<Concept>();
						newcd.addAll(s2);
						newcd.add(d);
						Concept cd = new AndConcept(newcd);
						Concept test = Util.parseConceptFromGeneralRolePath(
								grp, cd);
						ConceptAssertion rhs = new ConceptAssertion(
								ca.getIndividual(), test);
						if (Util.assertionCheck(ca, rhs, kb)) {
							// System.out.println("testing: "+ca.toString()+" -> "+rhs.toString());
							result.add(cd);
							// HashSet<Concept> hs = new HashSet<Concept>();
							// hs.addAll(s2);
							// hs.add(d);
							// //add as result
							// Concept cp = null;
							// if(hs.size()>1){
							// cp = new AndConcept(hs);
							// }else{
							// cp = hs.iterator().next();
							// }
							// result.add(cp);
						}
					}
					j++;
				}

			}
			i++;
		}
		return result;
	}

	// given subres1 whose size =1 , and subres2, do a quick check
	protected List<Concept> quickResultProcessing(List<Concept> small,
			List<Concept> other, ConceptAssertion ca, GeneralRolePath grp) {
		List<Concept> result = new LinkedList<Concept>();
		Concept singleton = small.get(0);
		result.add(singleton);
		boolean nopair = true;
		for (Concept ad : other) {
			Concept cd = new AndConcept(singleton, ad);
			Concept test = Util.parseConceptFromGeneralRolePath(grp, cd);
			ConceptAssertion rhs = new ConceptAssertion(ca.getIndividual(),
					test);
			if (Util.assertionCheck(ca, rhs, kb)) {
				result.add(ad);
				nopair = false;
			}
		}
		if (nopair || other.size() == 0) {
			result.add(KBVocabulary.CONCEPT_TOP);
		}
		return result;
	}

	// private List<Concept> projectJoin(ConceptAssertion ca,
	// ProjectionDescription pd1,
	// ProjectionDescription pd2, GeneralRolePath grp) throws
	// ProjectionException {
	// List<Concept> result = new LinkedList<Concept>();
	// List<Concept> outer = project(ca, pd1, grp);
	// Concept top = Util.parseConcept("TOP");
	// if (outer.isEmpty()) {
	// outer.add(top);
	// }
	// for (Concept c1 : outer) {
	// // c1 = testMissingFeatureValue(c1);
	// GeneralRolePath mygrp = grp.newCopy();
	// if (ENABLE_OPTIMIZATIONS) {
	// //rp.setConcept(c1);
	// mygrp.addContent(c1);
	// }
	// List<Concept> inner = project(ca, pd2, mygrp);
	// if (inner.isEmpty()) {
	// inner.add(top);
	// }
	// for (Concept in : inner) {
	// // in = this.testMissingFeatureValue(in);
	// result.add(new AndConcept(c1, in));
	// }
	// // grp.setConcept(null);
	// }
	// return result;
	// }

	// private Concept testMissingFeatureValue(Concept c1) {
	// if(allowMissingFeaturePatching){
	// if(c1 instanceof DomainConceptEQ){
	// String s = (String) ((DomainConceptEQ<?, ?>) c1).getRealValue();
	// if(s.equals(KBVocabulary.FeatureValueMissingPatch)){
	// return KBVocabulary.CONCEPT_TOP;
	// }
	// }
	// }
	// return c1;
	// }

	private List<Concept> projectRole(ConceptAssertion ca, Role role,
			ProjDesc pd, GeneralRolePath grp)
			throws ProjectionException {
		List<Concept> result = new LinkedList<Concept>();
		GeneralRolePath mygrp = grp.newCopy();
		mygrp.addContent(role);
		// because the join procedure produce maximum results, there is a need to
		// reduce s1 in advance
		List<Concept> s1 = project(ca, pd, mygrp);
		s1 = reduce(s1, grp, this.kb);
		s1 = reduce(s1, grp, null);
		// Empty inner result case
		if (s1.isEmpty()) {
			// Concept top = Util.parseConcept("TOP");
			Concept top = KBVocabulary.CONCEPT_TOP;
			Concept rhs = Util.parseConceptFromGeneralRolePath(mygrp, top);
			ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(), rhs);
			if (Util.assertionCheck(ca, ast, kb)) {
				result.add(new ExistsConcept(role, top));
			} else {
				result.add(top);
			}
			return result;
		}

		// General case
		LinkedList<HashSet<Concept>> q = new LinkedList<HashSet<Concept>>();
		// initialize q
		for (Concept con : s1) {
			HashSet<Concept> hs = new HashSet<Concept>();
			hs.add(con);
			q.add(hs);
		}

		// build results
		while (!q.isEmpty()) {
			HashSet<Concept> s2 = q.removeLast();
			boolean notgrown = true;
			List<Concept> cans = getCandaditesLexographic(s1, s2);
			for (Concept can : cans) {
				HashSet<Concept> newSet = new HashSet<Concept>(s2);
				newSet.add(can);
				Concept nested = null;
				if (newSet.size() > 1) {
					nested = new AndConcept(newSet);
				} else {
					nested = newSet.iterator().next();
				}

				Concept rhs = Util.parseConceptFromGeneralRolePath(mygrp,
						nested);
				ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(),
						rhs);
				if (Util.assertionCheck(ca, ast, kb)) {
					q.add(newSet);
					notgrown = false;
				}
			}
			if (notgrown) {
				Concept filler = null;
				if (s2.size() > 1) {
					filler = new AndConcept(s2);
				} else {
					filler = s2.iterator().next();
				}
				Concept rhs = Util.parseConceptFromGeneralRolePath(mygrp,
						filler);
				ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(),
						rhs);
				if (Util.assertionCheck(ca, ast, kb)) {
					result.add(new ExistsConcept(role, filler));
				}

			}
		}
		if (result.size() < 1) {
			result.add(KBVocabulary.CONCEPT_TOP);
		}
		return reduce(result, grp, this.kb);
	}

	// Get all 'cans' that are lexographically ordered after all constraints
	private static List<Concept> getCandaditesLexographic(List<Concept> cans,
			HashSet<Concept> constraints) {
		List<Concept> result = new LinkedList<Concept>();
		for (Concept c : cans) {
			boolean add = true;
			for (Concept d : constraints) {
				if (c.toString().compareTo(d.toString()) <= 0) {
					add = false;
					break;
				}
			}
			if (add) {
				result.add(c);
			}
		}
		return result;
	}

	// Reduce concept set to get most specific only
	private List<Concept> reduce(List<Concept> set, GeneralRolePath grp,
			DescriptionLogicsKB kb) {
		List<Concept> result = new LinkedList<Concept>();
		for (Concept c : set) {
			boolean minimal = true;
			for (Concept c2 : set) {
				if (c.equals(c2)) {
					continue;
				}
				Concept lhs = Util.parseConceptFromGeneralRolePath(grp, c2);
				Concept rhs = Util.parseConceptFromGeneralRolePath(grp, c);
				// System.out.println(lhs+"-->"+rhs);
				boolean sat = false;
				try {
					sat = Util.subsumes(lhs, rhs, kb);
				} catch (Exception e) {
					// System.out.println(lhs+"-->"+rhs+"; "+kb.toString());
					e.printStackTrace();
				}
				if (sat) {
					if (Util.subsumes(rhs, lhs, kb)) {
						if (ChooseLongestEqConcept) {
							// if c2=c, choose the longest one.
							if (c2.toString().compareTo(c.toString()) > 0) {
								minimal = false;
								break;
							}
						}
					} else {
						minimal = false;
						break;
					}

				}
			}
			if (minimal) {
				result.add(c);
			}
		}
		return result;
	}

}
